package megamu.mesh;

import java.util.ArrayList;
import java.util.LinkedHashMap;

import quickhull3d.QuickHull3D;

import com.jellyfishumbrella.Site;
import com.jellyfishumbrella.Vertex;
import com.jellyfishumbrella.VoronoiInput;

public class Voronoi {
	public final double						TOO_CLOSE	= 5;
	public LinkedHashMap<String, Vertex>	mergedVerts	= new LinkedHashMap<String, Vertex>();
	float[][]								edges;
	Region[]								regions;

	public Voronoi() {

	}

	public void generateVoronoi(VoronoiInput<Site> baseSites) {
		VoronoiInput<Site> baseSites2 = new VoronoiInput<Site>();
		for (int i = 0; i < baseSites.size(); i++) {
			baseSites2.add(baseSites.get(i));
			for (int j = 0; j < baseSites.size(); j++) {
				if (i != j) {
					double dx = ((Site) baseSites.get(i)).x - ((Site) baseSites.get(j)).x;
					double dy = ((Site) baseSites.get(i)).y - ((Site) baseSites.get(j)).y;
					double dz = ((Site) baseSites.get(i)).z - ((Site) baseSites.get(j)).z;
					double dist = Math.sqrt(dx * dx + dy * dy + dz * dz);
					if (dist < TOO_CLOSE) {
						System.out.println(baseSites.size()+"   " + i + "  " + j + "  " + dist +  "too close");
						baseSites2.remove(baseSites.get(i));
					}
				}
			}
		}
		
		baseSites = baseSites2;

		if (baseSites == null) {
			edges = new float[0][4];
			regions = new Region[0];
			return;
		}

		// build points array for qhull
		System.out.println(baseSites.size() + "   " + (baseSites.size() * 3 + 9));
		double qPoints[] = new double[baseSites.size() * 3 + 9];
		System.out.println(qPoints.length);
		for (int i = 0; i < baseSites.size(); i++) {
			Site currSite = (Site) baseSites.get(i);
			qPoints[i * 3] = currSite.x;// points[i][0];
			qPoints[i * 3 + 1] = currSite.z;// points[i][1];
			qPoints[i * 3 + 2] = -(currSite.x * currSite.x + currSite.z * currSite.z); // standard
																						// half-squared
																						// euclidian
																						// distance
		}
		// 1
		qPoints[qPoints.length - 9] = -8000D;
		qPoints[qPoints.length - 8] = 0D;
		qPoints[qPoints.length - 7] = -64000000D;
		// 2
		qPoints[qPoints.length - 6] = 8000D;
		qPoints[qPoints.length - 5] = 8000D;
		qPoints[qPoints.length - 4] = -128000000D;
		// 3
		qPoints[qPoints.length - 3] = 8000D;
		qPoints[qPoints.length - 2] = -8000D;
		qPoints[qPoints.length - 1] = -128000000D;

		// prepare quickhull
		QuickHull3D quickHull = new QuickHull3D(qPoints);
		int[][] faces = quickHull.getFaces(QuickHull3D.POINT_RELATIVE + QuickHull3D.CLOCKWISE);
		int artifact = 0;

		// compute dual points
		Vertex dualVerts[] = new Vertex[faces.length];
		for (int i = 0; i < faces.length; i++) {

			// test if it's the artifact
			if (faces[i][0] >= baseSites.size() && faces[i][1] >= baseSites.size() && faces[i][2] >= baseSites.size())
				artifact = i;

			double x0 = qPoints[faces[i][0] * 3 + 0];
			double y0 = qPoints[faces[i][0] * 3 + 1];
			double x1 = qPoints[faces[i][1] * 3 + 0];
			double y1 = qPoints[faces[i][1] * 3 + 1];
			double x2 = qPoints[faces[i][2] * 3 + 0];
			double y2 = qPoints[faces[i][2] * 3 + 1];

			double v1x = 2 * (x1 - x0);
			double v1y = 2 * (y1 - y0);
			double v1z = x0 * x0 - x1 * x1 + y0 * y0 - y1 * y1;

			double v2x = 2 * (x2 - x0);
			double v2y = 2 * (y2 - y0);
			double v2z = x0 * x0 - x2 * x2 + y0 * y0 - y2 * y2;

			double tmpx = v1y * v2z - v1z * v2y;
			double tmpy = v1z * v2x - v1x * v2z;
			double tmpz = v1x * v2y - v1y * v2x;

			dualVerts[i] = new Vertex(tmpx / tmpz, 0.0, tmpy / tmpz);
			if (mergedVerts.containsKey(dualVerts[i].toString())) {
				dualVerts[i] = mergedVerts.get(dualVerts[i].toString());
				System.out.println("mergedVerts: " + mergedVerts.size());
			} else {
				mergedVerts.put(dualVerts[i].toString(), dualVerts[i]);
			}
		}
		System.out.println("total mergedVerts: " + mergedVerts.size() + "   " + dualVerts.length);

		// create edge/point/face network
		edges = new float[1][4];
		int edgeCount = 0;
		LinkedArray faceNet = new LinkedArray(faces.length);
		ArrayList<ArrayList<Integer>> pointBuckets = new ArrayList<ArrayList<Integer>>();// IntArray[baseSites.size()];
		for (int i = 0; i < baseSites.size(); i++)
			pointBuckets.add(new ArrayList<Integer>());// new IntArray();

		// discover edges
		for (int i = 0; i < faces.length; i++) {

			// bin faces to the points they belong with
			for (int f = 0; f < faces[i].length; f++)
				if (faces[i][f] < baseSites.size())
					pointBuckets.get(faces[i][f]).add(i);

			for (int j = 0; j < i; j++) {
				if (i != artifact && j != artifact && isEdgeShared(faces[i], faces[j])) {

					faceNet.link(i, j);

					if (edges.length <= edgeCount) {
						float[][] tmpedges = new float[edges.length * 2][4];
						System.arraycopy(edges, 0, tmpedges, 0, edges.length);
						edges = tmpedges;
					}

					edges[edgeCount][0] = (float) dualVerts[i].x;
					edges[edgeCount][1] = (float) dualVerts[i].z;
					edges[edgeCount][2] = (float) dualVerts[j].x;
					edges[edgeCount][3] = (float) dualVerts[j].z;
					edgeCount++;

				}
			}
		}

		// trim edges down
		float[][] tmpedges = new float[edgeCount][4];
		// for(int i=0; i<tmpedges.length; i++)
		// tmpedges[i] = edges[i];
		System.arraycopy(edges, 0, tmpedges, 0, tmpedges.length);
		edges = tmpedges;

		// calculate the region for each point
		regions = new Region[baseSites.size()];
		for (int i = 0; i < baseSites.size(); i++) {
			// IntArray faceOrder = new IntArray(pointBuckets.get(i).size());
			ArrayList<Integer> faceOrder = new ArrayList<Integer>();

			// add coords of the region in the order they touch, starting with
			// the convenient first
			int p = pointBuckets.get(i).get(0);
			while (p >= 0) {

				faceOrder.add(p);

				// find the next coordinate that is in this set that we haven't
				// used yet
				int newP = -1;
				for (int k = 0; k < faceNet.get(p).links.size(); k++) {
					int neighbor = faceNet.get(p).links.get(k);
					if (!faceOrder.contains(neighbor) && pointBuckets.get(i).contains(neighbor)) {
						newP = neighbor;
						break;
					}
				}
				p = newP;

			}

			// turn the coordinates into a polygon
			regions[i] = new Region(pointBuckets.get(i).size());
			for (int f = 0; f < faceOrder.size(); f++) {
				int face = faceOrder.get(f);
				regions[i].add(dualVerts[face]);
			}
			regions[i].site = (Site) baseSites.get(i);
			regions[i].pointNormalsUp();
		}

	}

	public Region[] getRegions() {
		return regions;
	}

	public ArrayList<Edge> getEdges() {
		// return edges;
		ArrayList<Edge> edgeList = new ArrayList<Edge>();
		for (int i = 0; i < edges.length; i++) {
			Edge newEdge = new Edge();
			newEdge.vert1 = new Vertex(edges[i][0], 0.0, edges[i][1]);
			newEdge.vert2 = new Vertex(edges[i][2], 0.0, edges[i][3]);
			edgeList.add(newEdge);
		}
		return edgeList;
	}

	protected boolean isEdgeShared(int face1[], int face2[]) {
		for (int i = 0; i < face1.length; i++) {
			int cur = face1[i];
			int next = face1[(i + 1) % face1.length];
			for (int j = 0; j < face2.length; j++) {
				int from = face2[j];
				int to = face2[(j + 1) % face2.length];
				if (cur == from && next == to || cur == to && next == from)
					return true;
			}
		}
		return false;
	}

}
